package 二叉树相关问题;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//652
public class 寻找重复的子树 {

    List<TreeNode> res = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    //对一颗二叉树进行序列化
    private String traverse(TreeNode root) {
        if (root==null)
            return "#";
        String left=traverse(root.left);
        String right=traverse(root.right);
        String sub=left+","+right+","+root.val;
        int num = map.getOrDefault(sub, 0);
        if (num==1)
            res.add(root);
        map.put(sub,num+1);
        return sub;
    }

}
